1. Field of the Invention
The present invention pertains to security for navigation, positioning, and localization systems, and applications of cryptography thereto. The security can be applied to navigation, aircraft landing guidance, air traffic control, location-based access control, the prevention of relay attacks against financial and legal transaction protocols and protection of other data transmissions.
2. Description of the State of the Art
The general notion of positioning by distance and direction predates humanity. Radar and sonar, developed around the time of World War II, were the first human techniques that calculated distance by measuring the time of flight of a signal and combined distance and direction to give relative position; lidar systems later applied the same concept to the optical spectrum. The first combined distance-direction technology designed specifically for positioning and navigation was VHF Omnidirectional Range/Distance Measuring Equipment (VOR/DME), deployed from 1948 to the present. Tactical Air Navigation (TACAN), an improved military version of VOR/DME using essentially the same methods, was built out in the early 1950s. Secondary surveillance radar, also known as Air Traffic Control Radio Beacon System (ATCRBS), introduced in the late 1950s, was an important refinement. Most direction-measurement protocols measure horizontal (azimuth) angle; the glide-slope indicator component of instrument Landing Systems (ILS), introduced in the 1940s, added rough indication of vertical (elevation) angle, and Microwave Landing Systems (MLS), introduced in the 1980s, added precise measurement of elevation angle.
Identification Friend or Foe (IFF) interrogators and transponders built into some aircraft during and after World War II were distance-angle radiolocation systems with rudimentary security mechanisms. Cryptographic security was first added to IFF in IFF Mark XII, a.k.a. Mode 4, in the 1960s, which provides only imprecise distance/angle information and is intended to identify aircraft that are located using radar or other means; Mark XII also provides little protection against relay attacks. Mark XIIA, a.k.a. Mode 5, introduced in the 2000s, features improved transmission security and message security, but it identifies aircraft rather than locating the aircraft, and it appears not to use precise timing for distance bounding.
Secure distance bounding was first proposed in the academic literature by Beth et al., “Identification tokens, or: Solving the chess grandmaster problem”, Advances in Cryptology—Crypto '90, 1990, as a solution to relay attacks against cryptographic zero-knowledge authentication protocols; distance bounding was concretely described by Brands et al., “Distance-Bounding Protocols (Extended Abstract)”, Advances in Cryptology—Eurocrypt '93, 1993. U.S. Pat. No. 5,659,617 and its successor RE38,899 describe a method intended to provide security for radiolocation based on distance bounding.
Global Positioning System (GPS), the most common radionavigation system in use as of 2006, was developed by the U.S. military in the 1980s, and was the first widespread passive time-of-arrival navigation to include cryptographic security. The present generation of satellites offers two security mechanisms: Selective Availability adds a pseudorandom uncertainty to each satellite's range data, with the intent of denying high-resolution positioning information to unauthorized users; Anti-Spoofing additively encrypts the GPS precise positioning signal with a lower-frequency pseudorandom sequence, with the intent to both deny unauthorized use of that signal and to make spoofing of the signal difficult.
There has been a suggestion to protect positioning schemes based on simple directional receivability, received signal strength, or signal-to-noise ratio; however this does not provide the same security guarantee as time-of-flight techniques. The combination of secure distance bounding and direction-based positioning is described in Robust Position Estimation (ROPE), by Lazos et al., “ROPE: Robust Position Estimation in Wireless Sensor Networks”, Proceedings of the Fourth International Symposium on Information Processing in Sensor Networks (IPSN 2005), 2005.
Transmitting position messages with cryptographic protection was described in U.S. Pat. No. 4,077,005, and further described in association with the use of public-key algorithms in Desmedt, “Major security problems with the ‘unforgeable’ (Feige-) Fiat-Shamir proofs of identity and how to overcome them”, Proceedings of SecuriCom '88, 1988, and the aforementioned U.S. Pat. No. 5,659,617 and RE 38,899.
Passive time-of-flight navigation methods (e.g., those methods in which the node seeking to determine its position is a receiver only, such as GPS systems) are inherently vulnerable to several damaging relay attacks. Active methods not involving distance bounding are similarly vulnerable. Due to the hard minimum signal propagation time set by the speed of light, distance bounding offers a stronger proof of security. Using signal time of flight alone for secure positioning requires that at least three well-spaced non-collinear beacons be receivable from each point at which a node might need to be located. The combination of distance bounding and direction-based positioning can offer a degree of security that is unavailable with other positioning schemes that use a comparable number of nodes.
Navigation, proximity determination, and time synchronization are critical to numerous industrial and governmental activities. It is beneficial to provide such systems with security against position falsification (“spoofing”) and other forms of electronic attack.
Therefore, what is needed is a method and/or system to add provable cryptographic security to navigation and time-transfer protocols. There is also needed a method and/or system for decoupling time-dependent ranging messages from cryptographic algorithms responsible for security, in order to enable the use of pubic-key cryptographic functions. Furthermore, there is a need to add cryptographic security to direction-based navigation protocols. There is yet a further need for such methods and/or systems of cryptographic security that are efficient and cost-effective. The present invention satisfies these and other needs.